﻿// See https://aka.ms/new-console-template for more information
//快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移动到其右侧。具体来说，哨兵划分的流程为：
//1.选择数组最左端的元素作为基准数，初始化俩个指针i和j分别指向数组的两端
//2.设置一个循环，在每轮中使用i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素
//3.循环执行步骤2，知道i和j相遇时停止，最后将基准数交换至两个子数组的分界线
//哨兵划分完成后，原数组被划分为三部分：左子数组，基准数，右子数组，且满足“左子数组任意元素<=基准数<=右子数组任意元素”。因此，我们接下来只需要对这两个子数组进行排序。

int[] nums=new int[] { 1,22,33,12,123,1222,556,2347,93,778};
quickSort(nums,0,nums.Length-1);
foreach(var item in nums)
{
    Console.WriteLine(item);
}

void swap(int[] nums, int i, int j)
{
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

//哨兵划分
int partition(int[] nums, int left, int right)
{
    //以nums[left]作为基准数
    int i = left, j = right;
    while (i < j)
    {
        while (i < j && nums[j] >= nums[left])//从右向左找首个小于基准数的元素
            j--;
        while (i < j && nums[i] <= nums[left])//从左向右找首个大于基准数的元素
            i++;
        swap(nums, i, j);//交换两个元素
    }
    swap(nums, i, left);//将基准数交换至两子数组的分界线
    return i;//返回基准数的缩影
}

void quickSort(int[] nums, int left, int right)
{
    //子数组长度为1时终止递归
    if (left >= right)
        return;
    //哨兵划分
    int pivot = partition(nums, left, right);
    //递归左子数组，右子数组
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

